package algorithm.linkedlist;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/rotate-list/description/
 * Difficulty : Medium
 *
 * 轮转链表节点元素, 链表尾节点追加到头部
 *
 * @Author Antony
 * @Since 2018/7/16 17:20
 */
public class RotateList {

    public static void main(String[] args) {
        ListNode initNode = ListNode.initDate(new int[]{1,2,3,4});
        System.out.println(initNode.nodeString());
        System.out.println(rotateRight(initNode, 0).nodeString());


    }

    /**
     * beats 99.96% - 9ms
     * 思路：避免循环
     * 先遍历一遍链表，找到长度
     * 然后慢指针需要往后移动的长度就是 len-k-1 (如果k>len 那么 k=k%len)
     * 移动len-k-1 个长度后，找到的是 k 节点的前一个节点
     *
     * 此时，快指针已到队列尾，然后 fast.next = head 将其合并，然后再在找到的 slow指针处断开即可
     */
    public static ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        int len = 1;
        while(fast.next != null){
            fast = fast.next;
            len++;
        }

        int rotNum = len - k%len - 1;
        while(rotNum > 0){
            slow = slow.next;
            rotNum--;
        }

        // 一定要先把尾指针指到头部，否则slow.next会为空
        fast.next = head;
        ListNode result = slow.next;
        slow.next = null;

        return result;
    }


    /**
     * beats 1.37% - 207ms
     *
     * 思路：
     * 遍历一遍找到尾节点然后next到头节点 和 长度
     * 然后再遍历一遍找到 需要走的步长，再找到正确节点
     */
    public static ListNode rotateRight_slow(ListNode head, int k) {
        if(head == null){
            return null;
        }
        int length = 1;
        ListNode tail = head;
        while(tail.next != null){
            length++;
            tail = tail.next;
        }
        tail.next = head;

        // 算出从tail 节点向后走的步长
        // 注意如果rotate的长度大于链表长度，则说明走了一个循环，需要+length使其变为正数
        int p = length - k;
        while(p < 0){
            p +=length;
        }
        while(p > 0){
            tail = tail.next;
            p--;
        }
        ListNode result = tail.next;
        tail.next = null;
        return result;
    }

}
